∂16-May-84  1154	JDH  	elliptical pen problem  
Perhaps the simplest fix is not to advance p←r in

	@<Remove the line from |q| to |r|...@>=

but to instead check whether

	abs(right_u(p)*left_v(q) - right_u(q)*left_v(r)) = 1

at the start of

	@<Interpolate new vertices in the ellipse data structure...@>=

Another option that sounds better to me in the long run is to allow degenerate
lines of length 0 when constructing the pen, and add a separate pass afterward
to get rid of them.  This seems right to me since this is semantically what is
happening.  It would also having to artificially reduce |alpha| to avoid
degeneracy.  (I once objected to this.)

Of course what I secretly really want is the complex solution involving two
class numbers for each vertex.  This would get around the problem entirely...

∂13-May-84  1907	JDH  	Long message about transforming edges  
I came up with a pretty good algorithm for the hard case of transforming
edges, and I just couldn't resist coding it up.  I have not done anything
to debug it yet but I will if you want.

The algorithm requires very little extra storage and usually runs in linear
time (w.r.t. size of input plus output).  I say ``usually'' because a lot
of time could be spent scanning up and down the row headers if the edge
structure was built from a very large number of separate contours.



@ The last and most difficult routine for transforming edge structures is
|xy_swap_edges| which performs the transformation $T(x,y)=(y,x)$.  The
horizontal run lengths in the edge structure are mapped into vertical run
lengths.  We must create an edge structure that gives each pixel the same
weight as the vertical run lengths would.

Given any two adjacent rows of an edge structure, we can determine what
{\sl horizontal\/} edges would be required to delineate vertically adjacent
pixels of differing weights.  Thus we scan the rows of the existing edge
structure from the top down adding edge nodes at the left ends of the rows
of the new structure.  We maintain a linked list of pointers to rows of the
new structure corresponding to the positions of edges in the current row of
the old structure.  These pointers only move when edges are added to the
new structure.

@p procedure xy_swap_edges
label continue;
var p,q,r,s,b: pointer; {pointers that traverse the original structure}
    a: pointer;		{traverses a list of active rows in new structure}
    pp, qq: pointer;	{pointers that traverse the new structure}
    tt: integer;	{value of $m$ corresponding to top of new structure}
    m0,m1,m2,mm: integer; {values of $m$ for edges in current row}
    n:integer;		{value of $n$ that splits rows |p| and |q|}
    w1,w2,w,ww: integer; {pixel weights}
begin @<Change the header |cur_edges| to account for the transformation@>;
@<Initilize new structure to empty and prepare |p| and |q| for generating
  for generating the last column of the new structure and add an empty row
  |b| at the bottom@>;
repeat link(temp_head)←null;
	q←knil(q); p←q;
	@<Add the column generated by rows |p| and |q| to the new structure
	  and update the active list@>;
	flush_list(sorted(p)); free_node(row_nodesize,p);
until q=b;
free_node(row_node_size, b);
end;

@ We must swap |m_min| and |m_max| with |n_min| and |n_max|, taking
|m_offset| into account.  The new structure will be constructed with
|m_offset(cur_edges)=zero_field|.  We can afford to update
|m_offset(cur_edges)| immediately since we will only deal with relative
horizontal coordinates.

@<Change the header |cur_edges|...@>=
n←n_max(cur_edges);
p←m_min(cur_edges); m_min(cur_edges)←n_min(cur_edges);
q←m_max(cur_edges); m_max(cur_edges)←n_max(cur_edges);
n_min(cur_edges)←p-m_offset(cur_edges)+zero_field;
n_max(cur_edges)←q-m_offset(cur_edges)+zero_field;
n_pos(cur_edges)←n_max(cur_edges)+1;
n_rover(cur_edges)←cur_edges;
m_offset(cur_edges)←zero_field;
last_window_time(cur_edges)←0

@ We add empty rows at the top and bottom of the old structure to make it
easier to find the top and bottom rows of horizontal pixels.

@<Initilize new structure to empty and prepare |p| and |q|...@>=
q←get_node(row_node_size);
knil(q)←knil(cur_edges); sorted(q)←sentinel;
b←get_node(row_node_size);
sorted(b)←sentinel; knil(link(cur_edges))←b;
link(cur_edges)←cur_edges; knil(cur_edges)←cur_edges;
tt←-4096

@ We scan the edge-weight nodes in the two current rows keeping track of
the total edge weight in each.  Horizontal edges are needed in ranges where
these differ.  Pointers in the active list enable us to find the rows in
the new structure where these edges should be added.

@<Add the column generated by rows |p| and |q|...@>=
w1←0; w2←0;
p←sorted(p); r←sorted(q); a←temp_head;
m1←ho(info(p)) div 8; m2←ho(info(r)) div 8;
pp←cur_edges;
while p≠sentinel or r≠sentinel do
	begin @<Advance |p| or |r| updating the pixel weights and the
		active list, and set |m0| to the number of pixels passed@>;
	if w1≠w2 then 
		@<Add a new edge of weight |w2-w1| to the next |m0| rows
		  above |pp|@>;
	end;
if w1≠w2 then confusion("9"); {fixthis: might want to remove this test}
n←n-1

@ The active list now contains one entry for each vertical edge in the row
of~|p|; at the end of the current loop it should have one entry for each
edge in row~|q|.  Thus we delete from the active list when we advance~|p|,
and we insert new entries when we advance~|r|.

@<Advance |p| or |r| updating the pixel weights...@>=
if w1=w2 then
   if link(a)=null then begin pp←cur_edges; mm←tt; end
   else begin pp←info(link(a)); mm←m1; end;
@<Move |pp| downward until |mm≤m1 and mm≤m2|@>;
if m1<m2 or r=sentinel then
	begin w1←w1+ho(info(p)) mod 8;
	m0←m2-m1; p←link(p); m1←ho(info(p)) div 8;
	s←link(a); link(a)←link(s); free_avail(s);
	end
else	begin w2←w2+ho(info(r)) mod 8;
	m0←m1-m2; r←link(r); m2←ho(info(r)) div 8;
	s←get_avail; info(s)←pp; link(s)←link(a); link(a)←s;
	end;

@ @<Move |pp| downward until...@>=
while mm>m1 or mm>m2 do
	if knil(pp)≠cur_edges then pp←knil(pp);
	else begin qq←get_node(row_node_size);
		sorted(qq)←sentinel; unsorted(qq)←null;
		knil(pp)←qq; link(qq)←pp;
		knil(qq)←cur_edges; link(cur_edges)←qq;
		pp←qq;
		end

@ When we add edges to the new structure, it may be necessary to add new
rows at the top.

@<Add a new edge of weight |w2-w1|...@>=
while m0>0 do
	begin if link(pp)≠cur_edges then pp←link(pp)
	else	begin qq←get_node(row_node_size);
		sorted(qq)←sentinel; unsorted(qq)←null;
		link(pp)←qq; knil(qq)←pp;
		link(qq)←cur_edges; knil(cur_edges)←qq;
		pp←qq;
		end;
	ww←w2-w1;
	if ww>0 then w←3 else w←-3;
	while ww≠0 do
		begin if abs(ww)<3 then w←ww;
		qq←get_avail;
		info(qq)←8*n+zero_w+w;
		link(qq)←sorted(pp); sorted(pp)←qq;
		ww←ww-w;
		end;
	end